//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 
// 
// 
// 
// Related Topics 数组 回溯 👍 1078 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * Java：N 皇后
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P51_NQueens {
    public static void main(String[] args) {
        Solution solution = new P51_NQueens().new Solution();
        for (int i = 1; i <= 9; i++) {
            MyUtil.printf("{}皇后：{}", i, solution.solveNQueens(i));
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> list = new ArrayList<>(n);
            if (n <= 0) {
                return list;
            }
            process(0, new int[n], list);
            return list;
        }

        /**
         * 当前来到第i行，i-1及以上的决定放在record数组中，返回能放下的方法数
         * record[x]=y表示第x行的皇后放在了y列上
         */
        private void process(int i, int[] record, List<List<String>> list) {
            // 总列数
            int N = record.length;
            // 能来到最后表示前面的都有效
            if (i == N) {
                list.add(transfer(record));
                return;
            }
            // 枚举皇后在每列的情况
            for (int j = 0; j < N; j++) {
                if (valid(record, i, j)) {
                    record[i] = j;
                    process(i + 1, record, list);
                }
            }
        }

        /**
         * 排列好的皇后转成[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]的形式
         */
        private List<String> transfer(int[] record) {
            int N = record.length;
            List<String> list = new ArrayList<>(N);
            // 行从上到下
            for (int i = 0; i < N; i++) {
                // 每个结果先统一用'.'填充
                StringBuilder sb = new StringBuilder();
                for (int k = 0; k < N; k++) {
                    sb.append('.');
                }
                // 单独填充皇后的位置
                sb.setCharAt(record[i], 'Q');
                list.add(sb.toString());
            }
            return list;
        }

        /**
         * 判断 [i,j]位置的皇后是否合理
         */
        private boolean valid(int[] record, int i, int j) {
            for (int k = 0; k < i; k++) {
                // 共列
                if (j == record[k]) {
                    return false;
                }
                // 共斜线
                if (Math.abs(i - k) == Math.abs(j - record[k])) {
                    return false;
                }
            }
            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}